package first_practice;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-15-三数之和
 * @date 2025/4/14 11:11
 */
public class Solution15 {
    public static List<List<Integer>> threeSum(int[] nums) {
        int length = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < length - 2; i++) { // 外层循环枚举第一个数
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳过重复数字
            if (nums[i] + nums[length - 1] + nums[length - 2] < 0) continue; // 当前i太小
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break;// 当前i太大
            // 双指针求解twoSum
            int L = i + 1, R = length - 1;
            while (L < R) {
                int s = nums[i] + nums[L] + nums[R];
                if (s > 0) {
                    R--;
                } else if (s < 0) {
                    L++;
                } else {
                    ans.add(List.of(nums[i], nums[L], nums[R]));
                    // 还需要考虑L和R的重复元素
                    for (L++; L < R && nums[L] == nums[L - 1]; L++) ; // 跳过重复数字
                    for (R--; L < R && nums[R] == nums[R + 1]; R--) ; // 跳过重复数字
                }
            }
        }
        return ans;
    }
}
